Two lower bound arguments with “inaccessible” numbers

The lirst result presented in this paper is a lower bound of Q(log n) for the computation time of concurrent-write parallel random access machines (PRAMS) with operation set { +, multiplication by constants} that recognize the “threshold set ” {X E Z ” 1 x1 +... +,Y, <xn} for inputs from (0, 1, 2,.... 2 o(“-i”rn)}“. The same bound holds for PRAMS with arbitrary binary operations, if the size of the input numbers is not restricted. The second lower bound regards languages in R ” corresponding to KNAPSACK, MINIMUM PERFECT MATCHING, SHORTEST PATH, and TRAVELING SALESPERSON on linear decision trees (LDTs) with the restriction that the number of negative coefficients a, in each test zz, <,<,, a,xi: a,, is bounded by f(n). The lower bounds on the depth of such LDTs that recognize these languages are 51(2 L”‘*/‘“‘J) for KNAPSACK and 52(2LA’4J(“)J) for the graph problems. The common new tool in the proofs of these lower bounds is the method of constructing “hard ” instances (x,,.... x,) of the respective problem by building up the input numbers xi from “mutually inaccessible ” numbers, i.e., numbers of different orders of magnitude. 0 1988 Academic Press, Inc. 1